package leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Created by Ghost on 2014/11/18 0018.
 */
public class Word_Break_II {
    private LinkedList<String> lst = new LinkedList<String>();
    private LinkedList<String> rst = new LinkedList<String>();
    private void add(String s, int[][] w, int begin){
        StringBuilder a = new StringBuilder("");
        if(begin==w.length){

            String[] ws = lst.toArray(new String[lst.size()]);
            for(int i=0;i<ws.length;i++){
                if(i==0)
                    a.append(ws[i]);
                else{
                    a.append(" ").append(ws[i]);
                }
            }
            rst.add(a.toString());
            return ;
        }
        for(int i=begin;i<w.length;i++){
            if(w[begin][i]==1){
                lst.add(s.substring(begin,i+1));
                add(s,w,i+1);
                lst.removeLast();
            }
        }
    }
    public List<String> wordBreak(String s, Set<String> dict) {
        int m = s.length();
        int[][] w = new int[m][m];
        for(int i=0;i<m;i++){
            if(dict.contains(""+s.charAt(i)))
                w[i][i] = 1;
        }
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                boolean rst = dict.contains(s.substring(i,j+1));
                if(!rst){
                    rst = w[i][j-1]==1 && dict.contains(""+s.charAt(j));
                    if(rst)
                        w[i][j] = 1;
                }
                else
                    w[i][j] = 1;
            }
        }
        add(s,w,0);
        return rst;
    }

    public static void main(String[] args){
        Word_Break_II word_break_ii = new Word_Break_II();
        String s = "aaaaaaaab";
        Set<String> dict = new HashSet<String>();
        dict.add("a");
        dict.add("aaa");
        dict.add("aaaa");
        dict.add("aaab");

        List<String> a = word_break_ii.wordBreak(s, dict);
        for(String aa:a){
            System.out.println(aa);
        }
    }
}
